package com.itheima.leetcode.od.b.graph;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * (A卷,200分)- 计算网络信号、信号强度（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。
 * 注意:网络信号可以绕过阻隔物。
 * <p>
 * array[m][n] 的二维数组代表网格地图，
 * array[i][j] = 0代表i行j列是空旷位置;
 * array[i][j] = x(x为正整数)代表i行j列是信号源，信号强度是x;
 * array[i][j] = -1代表i行j列是阻隔物。
 * 信号源只有1个，阻隔物可能有0个或多个
 * 网络信号衰减是上下左右相邻的网格衰减1
 * 现要求输出对应位置的网络信号值。
 * <p>
 * 输入描述
 * <p>
 * 输入为三行，第一行为 m 、n ，代表输入是一个 m × n 的数组。
 * 第二行是一串 m × n 个用空格分隔的整数.
 * 每连续 n 个数代表一行，再往后 n 个代表下一行，以此类推。
 * 对应的值代表对应的网格是空旷位置，还是信号源，还是阻隔物。
 * 第三行是 i 、 j，代表需要计算array[i][j]的网络信号值。
 * 注意：此处 i 和 j 均从 0 开始，即第一行 i 为 0。
 * <p>
 * 例如
 * <p>
 * 6 5
 * <p>
 * 0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
 * <p>
 * 1 4
 * <p>
 * 代表如下地图
 * <p>
 * <p>
 * <p>
 * 需要输出第1行第4列的网络信号值，如下图，值为2。
 * <p>
 * 输出描述
 * <p>
 * 输出对应位置的网络信号值，如果网络信号未覆盖到，也输出0。
 * 一个网格如果可以途径不同的传播衰减路径传达，取较大的值作为其信号值。
 * <p>
 * 用例
 * <p>
 * 输入	6 5
 * <p>
 * 0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
 * <p>
 * 1 4
 * <p>
 * 输出	2
 * 说明	无
 * <p>
 * 输入	6 5
 * <p>
 * 0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 * <p>
 * 2 1
 * <p>
 * 输出	0
 * 说明	无
 */
public class BFSCalculateNetworkSignals {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        int[] arr = new int[m * n];
        for (int i = 0; i < m * n; i++) {
            arr[i] = sc.nextInt();
        }*/

        int m = 6;
        int n = 5;

        String input = "0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0";
        int[] arr = Arrays.stream(input.split(" ")).mapToInt(Integer::parseInt).toArray();

        int tarI = 1;
        int tarJ = 4;

        System.out.println(getResult(arr, m, n, tarI, tarJ));
    }

    public static int getResult(int[] arr, int m, int n, int tarI, int tarJ) {
        LinkedList<Integer[]> queue = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i * n + j] > 0) {
                    queue.offer(new Integer[]{i, j});
                    break;
                }
            }
        }

        // 上下左右偏移量
        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (queue.size() > 0) {
            Integer[] pos = queue.poll();
            int i = pos[0];
            int j = pos[1];

            int x = arr[i * n + j] - 1;

            if (x == 0) {
                break;
            }

            for (int[] offset : offsets) {
                int newI = i + offset[0];
                int newJ = j + offset[1];

                if (0 < arr[newI * n + newJ]) {
                    continue;
                }

                if (newI >= 0 && newI < m && newJ >= 0 && newJ < n && arr[newI * n + newJ] == 0) {
                    arr[newI * n + newJ] = x;
                    queue.offer(new Integer[]{newI, newJ});
                }
            }
        }

        return arr[tarI * n + tarJ];
    }
}